MAB 쉽게 알아보기

세 개의 슬롯머신 앞에서

당첨 확률이 서로 다른 슬롯머신 세 대가 있다. 각 확률은 20%, 30%, 15%지만 어떤 기계가 가장 잘 터지는지는 알 수 없다. 가진 동전은 100개뿐이다.

기계별 당첨률을 비교하는 것이 목적이라면 동전을 고르게 나눠 결과를 살펴볼 수 있다. 하지만 목표가 100번 동안 최대한 많이 당첨되기라면 이야기가 달라진다. 잘 터지는 듯한 기계를 더 자주 이용하되 초반 당첨이 우연인지 확인하려면 다른 기계도 계속 시도해야 한다. 이것이 탐색(Exploration)과 활용(Exploitation)의 문제다.

참고로 다중 선택지 밴딧(Multi-Armed Bandit, MAB)의 이름을 그대로 풀면, 서로 다른 당첨 확률을 가진 손잡이(Arm)가 여러 개 달린 가상의 슬롯머신 한 대에 가깝다. 슬롯머신을 One-Armed Bandit이라고 부르던 데서 유래했다.

실제 슬롯머신은 보통 손잡이가 하나라서 이번 글에서는 확률이 다른 슬롯머신 여러 대로 나눠 표현한다. 손잡이 하나를 고르든 기계 한 대를 고르든, 매번 선택지 하나를 고른다는 문제는 같다.

슬롯머신을 CTA로 바꿔 보기

앱의 메인 버튼 문구를 두 가지로 준비했다고 하자.

• CTA A: 무료로 시작하기
• CTA B: 지금 시작하기

사용자가 클릭하면 보상은 1, 클릭하지 않으면 0이다. 슬롯머신의 손잡이는 CTA가 되고, 당첨 여부는 클릭 여부가 된다.

이 글에서는 Variant 하나가 Arm 하나에 대응하고 방문자는 한 번만 선택 대상이 된다고 단순화한다.

bash
CTA 선택 → 노출 → 클릭 관측 → 정보 갱신 → 다음 CTA 선택

MAB는 어떤 머신러닝일까?

MAB는 어느 선택지가 가장 좋은지 알아가는 동안 누적 보상을 높이려는 의사결정 문제다. 지도 학습(Supervised Learning)은 입력과 정답이 함께 담긴 데이터로 모델을 훈련한다. 반면 MAB는 미리 준비된 정답지가 없다. CTA를 선택한 뒤 돌아온 클릭 정보(보상)를 보고 다음 선택을 배운다. 선택과 학습이 같은 시간축에서 일어나는 온라인 의사결정(Online Decision-Making) 문제인 셈이다.

CTA A를 보여주면 A의 클릭 여부만 알 수 있다. 같은 사용자에게 B를 보여줬다면 클릭 여부를 알 수 없다. 선택한 행동의 결과만 관측하는 제약을 부분 피드백(Partial Feedback)이라고 한다. 클릭을 보상으로 삼으면 CTA의 기대 보상은 장기적인 클릭률(CTR)이다. 이 글에서는 설명을 단순하게 하려고 실험 중 클릭률이 크게 변하지 않는 정상 환경(Stationary Environment)을 가정한다.

A/B 테스트와 무엇이 다를까?

A/B 테스트는 트래픽을 (통상적으로)50:50처럼 고정하고 데이터를 모아 효과 차이를 추정하고 검정하는 방식이다. 반면 MAB가 고정된 CTA만 보여주는 A/B 테스트와 차이는 결과에 따라 노출되는 CTA가 변경될 수 있다는 점이다. 성과가 좋은 CTA를 더 자주 노출하여 실험 기간의 누적 보상을 높이려 한다.

그림 1. A/B 테스트는 배분을 유지하고, MAB는 관측 결과로 다음 선택을 조정한다.

중요한 점은 어느 방법이 더 좋다의 문제가 아니라 실험 목적에 맞게 방법을 택하는 것이다. 정확한 효과 추정이 중요하면 A/B 테스트를, 학습 중의 성과까지 중요하면 MAB를 택할 수 있다.

탐색과 활용 사이에서

초반에 A와 B를 10명씩 보여주었더니 A는 2번, B는 1번 클릭됐다고 하자. 지금까지 관측한 클릭률은 A 20%, B 10%다. 이 결과만 보고 A를 계속 노출하는 행동이 활용으로 현재 최선으로 보이는 선택에서 보상을 얻는 방식이다. 하지만 실제 클릭률이 A 5%, B 6%라면 초반 결과가 우연히 뒤집혔던 셈인데, A에 트래픽을 모두 몰아버리면 B에 관한 정보는 더 이상 생기지 않는다. 즉 잘못된 의사결정으로 다른 선택지에 대한 데이터를 축적하지 못하는 문제가 발생한다. 이러한 점 때문에 B에 대한 시도도 유지해야 한다.

그림 2. 활용은 현재 보상을, 탐색은 더 나은 선택을 발견할 정보를 얻는다.

활용만 하면 초반의 우연에서 벗어나기 어렵고, 탐색만 하면 성과가 낮은 CTA에 트래픽을 낭비한다. MAB 알고리즘은 저마다 다른 방식으로 이 둘의 균형을 잡는다.

좋은 선택을 놓친 비용, Regret

Regret은 더 좋은 선택(optimal)을 알았다면 얻었을 보상과 실제로 얻은 보상의 차이다.
여기서 regret은 [optimal 선택의 reward]와 [특정 시점 선택의 reward]의 차이를 보여주는 지표로 아래 처럼 정의된다.

T는 전체 라운드 수, μ*는 optimal reward의 평균을 의미한다. regret이 후회를 의미하는 걸 고려하면, 탐색과 활용을 통해 후회를 최소화(minimal)하는 것이 자연스럽다.

방문자 100만 명, A의 실제 클릭률은 5%, B는 6%라고 사후적으로 가정해 보자. 처음부터 B만 보여주었다면 기대 클릭은 60,000회다.

50:50 배분의 기대 클릭은 55,000회다. 처음부터 B만 보여준 경우보다 5,000회를 놓쳤으므로 기대 Regret도 5,000이다.

가상 MAB 배분에서는 기대 클릭이 58,500회다. 50:50보다 기대 클릭을 3,500회 더 얻으면서 A도 계속 확인한 셈이다. 이때 기대 Regret은 1,500으로 줄어든다.

관측값을 다음 선택 기준으로 바꾸기

벼락치기 전날 먼저 공부할 챕터를 고른다고 해보자. 시험에 나올 가능성이나 남은 공부량처럼 저마다의 선택 기준이 필요하다. MAB도 마찬가지다. 다음 CTA를 고르려면 각 선택이 얼마나 좋은지 비교할 기준이 있어야 한다.

이 기준을 행동가치함수(Action-value Function)라고 한다. CTA b를 선택했을 때 평균적으로 얻을 보상, 곧 기대 보상을 나타낸다.

E는 기댓값, b는 하나의 CTA, k는 전체 CTA 수다. Q_*(b)의 *는 우리가 찾고 싶은 실제 기대 보상을 가리킨다. 이 값이 클수록 CTA b에서 평균적으로 더 많은 보상을 기대할 수 있다.

Regret을 줄이려면 행동가치가 큰 CTA를 찾아 자주 선택해야 한다.

문제는 실제 행동가치 Q_*(b)를 미리 알 수 없다는 점이다. 그래서 지금까지 관측한 평균 보상으로 값을 추정한다. 클릭을 보상으로 삼았다면 관측 클릭률이 행동가치의 추정치가 된다.

bash
CTA i의 기대 보상 추정치 = CTA i의 클릭 수 / CTA i의 노출 수

A의 노출이 400번, 클릭이 20번, B의 노출이 150번, 클릭이 9번이라고 가정하면 관측 평균 보상은 A 5%, B 6%다. 현재 기록만 보면 B가 앞서지만 A보다 관측 횟수가 적어 불확실성은 더 크다.

새 보상이 들어올 때마다 전체 기록을 다시 더할 필요는 없다. 기존 평균과 새 보상만 있으면 값이 갱신된다.

bash
새 평균 = 기존 평균 + (새 보상 - 기존 평균) / 새로운 노출 수

이제 각 CTA의 현재 성과가 보인다. 알고리즘은 이 추정치에 무작위 탐색을 섞거나 관측 횟수에서 불확실성을 계산해 다음 CTA를 고른다.

Thompson Sampling으로 CTA 고르기

이 글에서는 클릭처럼 보상이 0 또는 1인 문제에 Thompson Sampling을 적용한다. Thompson Sampling은 CTA의 클릭률을 하나의 고정된 추정값이 아니라, 아직 불확실성이 남아 있는 확률분포로 다룬다.

클릭 보상을 확률변수로 보기

베르누이 분포(Bernoulli Distribution)는 한 번의 시도에서 결과가 두 가지 중 하나로 나오는 상황을 표현한다. CTA에서는 클릭하면 보상 1, 클릭하지 않으면 보상 0이다.

CTA B의 실제 클릭 확률이 6%라고 해보자. 사용자가 B를 볼 때마다 6% 확률로 보상 1이 나오고, 나머지 94% 확률로 보상 0이 나온다.

bash
R(B) = 1: 6% 확률로 클릭
R(B) = 0: 94% 확률로 미클릭

클릭률이 6%라고 해서 사용자 100명 중 정확히 6명이 항상 클릭하는 것은 아니다. 실제 클릭 수는 매번 달라지지만, 노출을 아주 많이 반복하면 평균 보상은 0.06에 가까워진다.

이를 일반식으로 표현해보자. CTA b의 실제 클릭 확률을 θ_b라고 하면 보상 R(b)는 다음과 같은 베르누이 분포를 따른다.

bash
R(b) ~ Bernoulli(θ_b)
E[R(b)] = θ_b = Q_*(b)

~는 “이 확률분포를 따른다”는 뜻이다. E[R(b)]는 CTA b를 반복해서 보여줬을 때 얻는 평균 보상이다. 따라서 클릭 확률 θ_b는 앞에서 정의한 행동가치 Q_*(b)와 같다.

CTA B의 예시를 기댓값으로 직접 계산해도 같은 결과가 나온다.

bash
E[R(B)] = 1 × 0.06 + 0 × 0.94 = 0.06

문제는 θ_b를 미리 알 수 없다는 점이다. Thompson Sampling은 하나의 값으로 단정하는 대신 θ_b가 어떤 값일지 확률분포로 표현하고, 클릭 결과가 들어올 때마다 분포를 갱신한다.

클릭률에 베타분포를 사용하기

클릭률은 0과 1 사이의 값이다. 베타분포(Beta Distribution)도 0과 1 사이에서 정의되므로 클릭률의 불확실성을 표현하기 알맞다.

베타분포를 쓰는 또 다른 이유는 베르누이 분포의 켤레 사전분포(Conjugate Prior)이기 때문이다. 베타 사전분포에서 시작하면 클릭을 관측한 뒤의 사후분포도 베타분포가 된다. 분포의 종류를 바꾸지 않고 α와 β만 갱신하면 된다.

보상 R이 1이면 클릭이고 0이면 미클릭이다. 한 번의 결과를 관측한 뒤 사후분포는 다음과 같이 바뀐다.

bash
Beta(α, β) → Beta(α + R, β + 1 - R)

클릭 R=1:   Beta(α + 1, β)
미클릭 R=0: Beta(α, β + 1)

클릭이 s번, 미클릭이 f번 쌓였다면 사후분포는 Beta(α+s, β+f)가 된다. 처음에 별다른 정보가 없다면 모든 클릭률을 고르게 보는 Beta(1,1)에서 시작할 수 있다.

앞의 CTA 기록을 그대로 사용해보자. A는 400번 노출돼 20번 클릭됐으므로 Beta(21,381), B는 150번 노출돼 9번 클릭됐으므로 Beta(10,142)가 된다.

다음 CTA를 선택하는 방법

Thompson Sampling은 다음 방문자가 올 때 아래 과정을 반복한다.

bash
각 CTA의 사후분포에서 후보 클릭률을 하나씩 뽑는다
가장 큰 후보 클릭률이 나온 CTA를 노출한다
클릭 또는 미클릭을 관측한다
선택한 CTA의 α 또는 β를 1만큼 늘린다

관측이 적은 CTA의 분포는 넓어서 때때로 큰 후보값이 나온다. 덕분에 아직 충분히 확인하지 않은 CTA도 선택된다. 데이터가 쌓이면 분포가 좁아지고, 성과가 좋은 CTA를 선택하는 비율이 자연스럽게 높아진다.

이 과정에서 탐색과 활용이 별도의 고정 비율 없이 함께 일어난다. 다만 매번 뽑은 후보값은 해당 라운드의 선택을 위한 표본일 뿐, 그 자체가 실제 클릭률이나 통계적 신뢰도를 뜻하지는 않는다.

Feature Flag와 연결하기

사내에서 운영중인 Feature Flag와 MAB를 연동할 수 있을까 라는 물음에 이 글을 작성하게 됐다. 피쳐플래그는 feature의 변형 정의·타겟팅·전달·롤백을 맡는다. MAB 정책은 보상 기록을 보고 다음 CTA나 배분 비율을 정한다.

둘을 연결하면 선택 → 노출 기록 → 클릭 귀속 → 보상 집계 → 정책 갱신 순서의 피드백 루프가 만들어진다.

그림 4. 요청 시점의 전달·기록과 주기적인 집계·갱신을 나눈 피드백 루프.

전달 요청이 아니라 실제 화면에 표시된 노출을 기록해야 한다. 전달에 실패한 CTA까지 분모에 넣으면 클릭률이 왜곡된다. 관찰 구간이 끝나기 전에 미클릭을 0으로 확정하면 늦게 들어온 클릭도 놓친다.

Feature Flag의 가중치만 바꾼다고 MAB가 완성되지는 않는다. 어떤 선택에서 보상이 나왔는지 정책이 다시 받아야 학습이 이어진다.

의사결정 ID, Arm, 정책 버전, 선택 확률, 실제 노출과 보상을 연결해 기록한다. 70:30 같은 누적 노출 비율은 그 자체만으로 최선일 확률이나 통계적 유의성을 뜻하지 않는다.

사용자가 방문할 때마다 문구가 바뀌면 혼란스러울 수 있다. 이런 화면은 관찰 구간 동안 사용자별 CTA를 고정하는 편이 낫다.

MAB의 한계와 안전장치

• 트래픽이 적거나 차이가 작으면 불확실성이 오래 남는다. 알고리즘을 바꿔도 없던 정보가 생기지는 않는다.
• 클릭이 늦게 들어오거나 이벤트가 빠지면 잘못된 보상으로 학습한다. 특정 CTA의 이벤트만 더 자주 누락되면 측정 오류를 성과 차이로 받아들인다.
• 고전적인 MAB는 보상 분포가 크게 변하지 않는다고 가정한다. 계절, 유행, 요일에 따라 클릭률이 바뀌면 오래된 기록이 현재 선택을 방해할 수 있다.
• 적응형 배분 데이터에 일반 A/B 테스트의 p-value를 그대로 적용하면 해석이 어긋날 수 있다.
• 클릭만 보상으로 삼으면 구매나 장기 만족도가 낮아도 눈에 잘 띄는 CTA를 선호할 수 있다.

운영에는 최소 탐색 비율, 배분 변경 폭 제한, 즉시 중단 스위치(Kill Switch)가 필요하다. 오류율·지연 시간·구매 취소 같은 보호 지표(Guardrail Metric)도 함께 본다.

이 안전장치도 잘못 정의한 보상이나 누락된 이벤트를 고쳐주지는 않는다. 정책보다 먼저 측정과 롤백 경로를 믿을 수 있어야 한다.

그다음은 Contextual Bandit

일반 MAB는 모든 사용자에게 평균적으로 좋은 CTA를 찾는다. 맥락적 밴딧(Contextual Bandit)은 선택 전에 알 수 있는 사용자나 상황의 맥락(Context)을 함께 본다. 접속 시간, 기기, 신규 가입 여부 등이 맥락에 해당한다.

예를 들어 신규 사용자에게는 설명이 분명한 A가, 기존 사용자에게는 짧은 B가 더 잘 맞을 수 있다. Contextual Bandit은 이런 맥락 → Arm 관계를 데이터에서 학습한다. 실제로 보여준 CTA의 보상만 받는 부분 피드백은 그대로다.

맥락이 많아지면 모델과 데이터, 개인정보·편향 관리도 복잡해진다. 구체적인 알고리즘과 수식은 후속 글에서 다룬다.

MAB를 선택하기 전 체크리스트

처음에는 고정 배분으로 노출과 보상 귀속부터 검증하는 편이 안전하다. 측정 흐름을 신뢰할 수 있을 때 MAB 정책을 연결한다. 효과 차이를 추정하고 불확실성을 검정하는 것이 목표라면 고정 배분 A/B 테스트가 가깝다. 배우는 동안 놓치는 클릭까지 줄이고 싶다면 MAB가 답할 수 있는 문제다. 좋은 선택은 알고리즘 이름보다 보상 정의, 정확한 피드백, 운영 안전장치에서 시작한다.

Reference

• Reinforcement Learning: An Introduction, 2nd ed. — Sutton & Barto
• A Tutorial on Thompson Sampling — Russo et al.
• Multi-Armed Bandits and the Stitch Fix Experimentation Platform
• Multiple Multi-Armed Bandits — LaunchDarkly
• Why We Use Separate Tech Stacks for Personalization and Experimentation — Spotify Engineering
• Multi-Armed Bandit — HyeJinLee